import java.util.*;
public class test {
    //leetcode 32.最长有效括号
    class Solution {
        public static int longestValidParentheses(String s) {
            Deque<Integer> deque = new ArrayDeque<>();
            int len = 0;
            int maxlen = 0;
            deque.push(-1);
            for(int i = 0;i < s.length();i++){
                if(s.charAt(i) == '('){
                    deque.push(i);
                }else {
                    if(!deque.isEmpty()){
                        deque.pop();
                    }
                    if(deque.isEmpty()){
                        deque.push(i);
                    }else {
                        maxlen = i - deque.peek();
                        len = Math.max(len,maxlen);
                    }
                }
            }
            return len;
        }
    }
    //leetcode 1047.删除字符串中所有相邻重复项
    class Solution {
        public String removeDuplicates(String s) {
            Deque<Character> deque = new ArrayDeque<>();
            StringBuilder sb = new StringBuilder();
            for(int i = 0;i < s.length();i++){
                if(!deque.isEmpty() && deque.peek() == s.charAt(i)){
                    deque.pop();
                }else {
                    deque.push(s.charAt(i));
                }
            }
            while(!deque.isEmpty()){
                sb.append(deque.removeLast());
            }
            return sb.toString();
        }
    }
    //leetcode 278.第一个错误的版本
    public class Solution extends VersionControl {
        public int firstBadVersion(int n) {
            int left = 1;
            int right = n;
            while(left < right){
                int mid = left + (right - left) / 2;
                if(isBadVersion(mid)){
                    right = mid;
                }else {
                    left = mid + 1;
                }
            }
            return left;
        }
    }
    //leetcode 872.叶子相似的树
    class Solution {
        public boolean leafSimilar(TreeNode root1, TreeNode root2) {
            Deque<Integer> deque1 = new ArrayDeque<>();
            Deque<Integer> deque2 = new ArrayDeque<>();
            getLeaf(root1,deque1);
            getLeaf(root2,deque2);
            while(!deque1.isEmpty() && !deque2.isEmpty()){
                if(!deque1.pop().equals(deque2.pop())){
                    return false;
                }
            }
            return deque1.isEmpty() && deque2.isEmpty();
        }
        public void getLeaf(TreeNode root,Deque<Integer> deque){
            if(root == null){
                return;
            }
            if(root.left == null && root.right == null){
                deque.add(root.val);
            }
            getLeaf(root.left,deque);
            getLeaf(root.right,deque);
        }
    }
    //leetcode 897.递增排序搜索树
    class Solution {
        public TreeNode node;
        public TreeNode increasingBST(TreeNode root) {
            if(root.left == null && root.right == null){
                return root;
            }
            TreeNode count = new TreeNode(-1);
            node = count;
            creative(root);
            return count.right;
        }
        public void creative(TreeNode root){
            if(root == null){
                return;
            }
            creative(root.left);
            root.left = null;
            node.right = root;
            node = node.right;
            creative(root.right);
        }
    }
}
